package course.p3_arraysSort.exa09_bucketSort;

import course.p3_arraysSort.exa02_insertSort.InsertSort;

import java.util.Arrays;

public class IntBucketSort {

    /**
     * 桶排序实现
     * @param arr 目标数组
     * @param bucketSize 桶大小
     * @return
     */
    public int[] bucketSort(int[] arr,int bucketSize) {
        if(arr.length == 0) return arr;
        if(bucketSize == 0) return arr;
        int minValue = arr[0];
        int maxValue = arr[0];

        for(int value:arr) {
            if(value<minValue) {
                minValue = value;
            }
            else if(value>maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int)Math.floor((maxValue-minValue)/bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        for (int j : arr) {
            int index = (int) Math.floor((j - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], j);
        }

        int arrIndex = 0;
        for(int[] bucket: buckets) {
            if(bucket.length<=0) continue;
            for(int value:bucket) {
                arr[arrIndex++] = value;
            }
        }
        return arr;
    }

    /**
     * 自动扩容，并保存数据
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        if(arr.length==1){
            arr[arr.length - 1] = value;
        }
        else if(arr.length>1) {
            arr[arr.length - 1] = value;
            InsertSort.insertSort(arr);
        }
        return arr;
    }


}
